{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "45e81524",
   "metadata": {},
   "source": [
    "### 贴门牌号"
   ]
  },
  {
   "cell_type": "raw",
   "id": "a47d4851",
   "metadata": {},
   "source": [
    "# 从1到2020中这些数字中有多少个2（注意：不是问多少个数字里有2）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f61bfacd",
   "metadata": {},
   "outputs": [],
   "source": [
    "num = 0\n",
    "for i in range(1, 2021):\n",
    "    string = str(i)\n",
    "    num += string.count('2')\n",
    "    \n",
    "print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbd57f0b",
   "metadata": {},
   "source": [
    "### 2020"
   ]
  },
  {
   "cell_type": "raw",
   "id": "ee7fa6d5",
   "metadata": {},
   "source": [
    "在一个给定的由数字 '0' 和 '2' 组成的矩阵中寻找横向往右、纵向往下和斜向往右下的 '2020' 排列，\n",
    "原题中给定的矩阵是300行300列的，在一个txt文件中存放"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "13c45e25",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "18\n"
     ]
    }
   ],
   "source": [
    "with open('test.txt', 'r') as f:\n",
    "    content = f.read()\n",
    "\n",
    "content = content.split('\\n')[:-1]\n",
    "\n",
    "count = 0\n",
    "for line in content:\n",
    "    count += line.count('2020')\n",
    "\n",
    "content = list(map(list, zip(*content)))\n",
    "\n",
    "content = [\"\".join(line) for line in content]\n",
    "\n",
    "for line in content:\n",
    "    count += line.count('2020')\n",
    "\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28bdceff",
   "metadata": {},
   "source": [
    "### 跑步"
   ]
  },
  {
   "cell_type": "raw",
   "id": "9ba55458",
   "metadata": {},
   "source": [
    "小明坚持每天跑步，正常情况下每天跑一公里，如果这一天是周一或者月初（每月的一号），那么小明就会跑两公里\n",
    "（如果这一天既是周一，又是月初，小明也是跑两公里），小明从2000年1月1日（周六）一直坚持到了2020年10月1日（周四），\n",
    "请你计算一下小明共跑了多少公里？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "11a09d0d",
   "metadata": {},
   "outputs": [],
   "source": [
    "from datetime import datetime, timedelta\n",
    "start = datetime.strptime('2000/01/01', '%Y/%m/%d')\n",
    "end = datetime.strptime('2020/10/01', '%Y/%m/%d')\n",
    "\n",
    "num = 0\n",
    "today = start\n",
    "while True:\n",
    "    if today == end:\n",
    "        break\n",
    "    \n",
    "    if today.day == 1:\n",
    "        num += 2\n",
    "    elif today.weekday() == 0:\n",
    "        num += 2\n",
    "    else:\n",
    "        num += 1\n",
    "    today = today + timedelta(1)\n",
    "    \n",
    "print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86ac4b9a",
   "metadata": {},
   "source": [
    "### 蛇形排列 "
   ]
  },
  {
   "cell_type": "raw",
   "id": "1b979525",
   "metadata": {},
   "source": [
    "在蛇形排列矩阵中，第20行第20列的数字是多少？蛇形排列方式如图所示"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5faa32c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "center = 1\n",
    "for i in range(20):\n",
    "    center += i *4\n",
    "    \n",
    "print(center)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7aa97d0d",
   "metadata": {},
   "source": [
    "### 冒泡排序"
   ]
  },
  {
   "cell_type": "raw",
   "id": "71b46301",
   "metadata": {},
   "source": [
    "对一个字符串，对它进行冒泡排序使其为升序，例如：对于lan，排序成 aln 需要交换一次（只能交换相邻的两个字母），对于qiao，排序成 aioq \n",
    "就需要交换4次。请找出冒泡排序时恰好需要交换100次的字符串，\n",
    "如果有多个字符串满足条件，则找出最短的那个，如果有多个满足条件而且还是最短的，则找出字典序最小的那个。"
   ]
  },
  {
   "cell_type": "raw",
   "id": "8234fb41",
   "metadata": {},
   "source": [
    "问题分析：长度为 n 的降序数组的冒泡排序交换次数是 (n-1) * n / 2 次，大于等于100的第一个数是 105 = (15-1) * 15 / 2，\n",
    "所以最短的长度肯定是15了，再考虑到字典序最小，则答案应该就是onmlkjihgfedcba排列而成的，字典序最小，\n",
    "就需要第一个字母的字典序尽可能小，然后才是第二个、第三个……，\n",
    "那么就把正数第六个字母提到前面，结果应该就是jonmlkihgfedcba（当时推出来以后没有拿程序验证一下 ，心里还是很没底的）"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e59009ee",
   "metadata": {},
   "source": [
    "### 成绩统计"
   ]
  },
  {
   "cell_type": "raw",
   "id": "6a064ab7",
   "metadata": {},
   "source": [
    "问题：给定 n 个学生的成绩，大于等于60的为及格，大于等于85的为优秀。请你统计这 n 名同学的及格率和优秀率。\n",
    "\n",
    "输入格式：第一行一个数n，表示接下来有n行数据，接下来n行每行一个数m，代表该学生的成绩。\n",
    "\n",
    "输出格式：两行，第一行一个数表示及格率，第二行一个数表示优秀率，都要求四舍五入。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "68965481",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "n = int(input())\n",
    "nums = [int(input()) for _ in range(n)]\n",
    "\n",
    "ok_rate = 0\n",
    "prefect_rate = 0\n",
    "for num in nums:\n",
    "    if num >= 60:\n",
    "        ok_rate += 1\n",
    "    if num >= 85:\n",
    "        prefect_rate += 1\n",
    "print(ok_rate/n)\n",
    "print(prefect_rate/n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1946bfc4",
   "metadata": {},
   "source": [
    "### 第七题. 单词分析"
   ]
  },
  {
   "cell_type": "raw",
   "id": "81700cc4",
   "metadata": {},
   "source": [
    "原问题：在给定的字符串中，计算出现次数最多的字母和它的出现次数，如果出现次数最多的字母同时有多个，则找出字典序最小的。\n",
    "\n",
    "输入格式：一行，代表所要统计的字符串\n",
    "\n",
    "输出格式：两行，第一行一个字符，是出现最多的字母，第二行一个整数，该字母的出现次数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f6b10a72",
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "string = input()\n",
    "\n",
    "count = [string.count(char) for char in string]\n",
    "\n",
    "n = max(count)\n",
    "print(string[count.index(n)])\n",
    "print(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "895949c7",
   "metadata": {},
   "source": [
    "### 数字三角形"
   ]
  },
  {
   "cell_type": "raw",
   "id": "226164fb",
   "metadata": {},
   "source": [
    "问题：在如下图所示的数字三角形中，我们需要从三角形顶部走到底部，在每一个数字处，我们可以选择向临近的右下或者临近的左下走，所经过的数字的总和称为路径和，请你计算从顶部到底部所有路线中最大的路径和为多少？同时要求这条路径选左下的次数和选右下的次数相差不能大于1。\n",
    "数字三角形\n",
    "\n",
    "输入格式：第一行一个整数 n ，代表数字三角形的阶数，接下来 n 行中，第 j 行有 j 个整数，代表数字三角形中的第 j 层，整数之间用空格分割。\n",
    "\n",
    "输出格式：一个整数，代表最大的路径和。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d0c766d7",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "n = int(input())\n",
    "\n",
    "nums = [list(map(int, input().split())) for _ in range(n)]\n",
    "\n",
    "dp = nums.copy()\n",
    "\n",
    "for i in range(1, n):\n",
    "    for j in range(i+1):\n",
    "        if j == 0:\n",
    "            dp[i][j] += dp[i-1][j]\n",
    "        elif j == i:\n",
    "            dp[i][j] += dp[i-1][j-1]\n",
    "        else:\n",
    "            dp[i][j] += max(dp[i-1][j],dp[i-1][j-1])\n",
    "if n&1:\n",
    "    print(dp[n-1][n//2])\n",
    "else:\n",
    "    print(max(dp[n-1][n//2-1],dp[n-1][n//2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3f221fe",
   "metadata": {},
   "source": [
    "### 平面划分"
   ]
  },
  {
   "cell_type": "raw",
   "id": "ff4f666a",
   "metadata": {},
   "source": [
    "问题：给出N条直线的斜率和截距，计算这些直线会将xy平面划分为多少个区域。\n",
    "\n",
    "如图中所示，这些直线将平面划分为了7个区域。\n",
    "\n",
    "输入格式：第一行一个数 n 代表直线的个数，接下来 n 行每行两个整数，分别代表斜率和截距。\n",
    "\n",
    "输出格式：一行一个整数，代表划分区域的个数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b2751f2e",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "n = int(input())\n",
    "\n",
    "lines = [tuple(map(int, input().split())) for _ in range(n)]\n",
    "\n",
    "lines = list(set(lines))\n",
    "\n",
    "from itertools import combinations\n",
    "lines_combination = list(combinations(lines, 2))\n",
    "\n",
    "pots = 0\n",
    "for combination in lines_combination:\n",
    "    if combination[0][0] != combination[1][0]:\n",
    "        pots += 1\n",
    "        \n",
    "print(n+pots+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3bb417a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "问题：在怪物猎人游戏中，玩家可以通过在装备上镶嵌宝珠来获得收益，一共有六件装备，每件装备上都有一定数量的镶嵌孔，每个镶嵌孔都有各自的等级，而宝珠也有等级，镶嵌孔只能镶嵌比自己等级低的宝珠。关于宝珠的说明，宝珠有系列划分，同系列的宝珠没有区别，每个系列的宝珠镶嵌到一定数量时，都会获得一定的收益，如下面举例：\n",
    "\n",
    "A系宝珠等级是1级，镶嵌数量是 1，2，3，4，5 时，获得的收益分别是 1，2，3，6，7。镶嵌数量超过5个时，收益仍然为7，镶嵌数量上限为5。\n",
    "\n",
    "B系宝珠等级是2级，镶嵌数量是 1，2，3，4 时，获得的收益分别是 2，5，8，15。镶嵌数量超过4个时，收益仍然为15。镶嵌数量上限为4，以下同理\n",
    "\n",
    "C系宝珠等级是2级，镶嵌数量是 1，2，3，4 时，获得的收益分别是 4，7，9，13。\n",
    "\n",
    "D系宝珠等级是3级，镶嵌数量是 1，2，3，4 时，获得的收益分别是 5，10，14，21。\n",
    "\n",
    "可以看到，你在每个系列上的收益只与你在这个系列上花费的镶嵌孔数量有关，例如对A系宝珠而言，镶嵌3颗时，单位镶嵌孔收益为3/3 = 1，镶嵌4颗时，单位收益为6/4 = 1.5，镶嵌5颗时，单位收益为7/5 = 1.4。等级越高的宝珠系列 单位收益越高（通常而言是这样），而同等级的宝珠系列（例如B系和C系）的单位收益则显得不相上下。现在需要你找出一套镶嵌方案使总收益最大，只输出这个最大收益值即可。\n",
    "\n",
    "输入格式：前六行代表装备上的镶嵌孔，每行第一个数代表当前装备的镶嵌孔数量，后面的数依次为镶嵌孔的等级。第七行一个整数n，代表有n个系列宝珠，接下来n行，每行代表一个系列，每行的第一个数代表当前系列宝珠的等级，第二个数代表镶嵌数量上限，接下来几个数从低到高依次代表可达到的收益。\n",
    "\n",
    "数据限制：镶嵌孔和宝珠的等级L不超过4，每个系列的镶嵌数量上限不超过7，系列的数量不超过10000，镶嵌孔的总数不超过300。\n",
    "\n",
    "输出格式：一个整数，代表最大收益。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "80ef762e",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "lanqiaobei",
   "language": "python",
   "name": "lanqiaobei"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
